package com.jack.leetcode.每日一题;

import java.util.*;
import java.util.stream.Collectors;

public class 单词接龙2 {

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        List<List<String>> ladders = findLadders(beginWord, endWord, wordList);
        ladders.forEach(l -> {
            l.forEach(s -> System.out.print(s + ","));
            System.out.println();
        });
    }

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        if (wordList.isEmpty() || !wordList.contains(endWord)) {
            return new ArrayList<>();
        }
        List<List<String>> result = new ArrayList<>();
        Map<String, Integer> wordId = new HashMap<>();
        List<String> idWord = new ArrayList<>();
        ArrayList<Integer>[] edges;
        int id = 0;
        for (String word : wordList) {
            if (!wordId.containsKey(word)) {
                wordId.put(word, id++);
                idWord.add(word);
            }
        }
        if (!wordId.containsKey(beginWord)) {
            wordId.put(beginWord, id++);
            idWord.add(beginWord);
        }
        edges = new ArrayList[idWord.size()];
        for (int i = 0; i < idWord.size(); i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < id; i++) {
            for (int j = i + 1; j < id; j++) {
                if (isOneCharDistance(idWord.get(i), idWord.get(j))) {
                    edges[i].add(j);
                    edges[j].add(i);
                }
            }
        }
        int dest = wordId.get(endWord);
        int[] cost = new int[id];
        for (int i = 0; i < id; i++) {
            cost[i] = Integer.MAX_VALUE;
        }

        Queue<ArrayList<Integer>> q = new LinkedList<>();
        ArrayList<Integer> tmpBegin = new ArrayList<>();
        tmpBegin.add(wordId.get(beginWord));
        q.add(tmpBegin);
        cost[wordId.get(beginWord)] = 0;

        while(!q.isEmpty()){
            ArrayList<Integer> now = q.poll();
            int last = now.get(now.size() - 1);
            if(dest == last){
                List<String> tmp = new ArrayList<>();
                for(int index : now){
                    tmp.add(idWord.get(index));
                }
                result.add(tmp);
            }else{
                for(int i=0;i<edges[last].size();i++){
                    int to = edges[last].get(i);
                    if(cost[last] + 1 <= cost[to]){
                        cost[to] = cost[last]+1;
                        ArrayList<Integer> tmp = new ArrayList<>(now);
                        tmp.add(to);
                        q.add(tmp);
                    }
                }
            }
        }
        return result;
    }

    private static boolean isOneCharDistance(String a, String b) {
        int m = a.length();
        int n = b.length();
        if (m != n) {
            return false;
        }
        int distance = 0;
        for (int i = 0; i < m; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                distance++;
            }
        }
        return distance == 1;
    }
}
